package leetcode.weekly.week335;

import leetcode.helper.H;

//Solution4Test
public class Solution4 {

	int mod = (int) 1e9 + 7;

	public int waysToReachTarget(int target, int[][] types) {
		int n = types.length;
		long[][] dp = new long[n + 1][target + 1];
		dp[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			int[] t = types[i - 1];
			int c = t[0], m = t[1];
			for (int j = 0; j <= c; j++) {
				int g = j * m;
				for (int k = g; k <= target; k++) {
					dp[i][k] += dp[i - 1][k - g];
					dp[i][k] %= mod;
				}
			}
		}
		return (int)dp[n][target];
	}

}
